package class04;


import java.util.ArrayList;

// 给定一颗二叉树的头节点，返回这颗二叉树中最大的二叉子树头节点
public class Code01_MaxSubBSTHead {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }

    public static class Info {
        /**
         * isBST 可以做调整
         * 如果搜索二叉树节点和树的节点树相等，说明，树一定是搜索二叉树
         */
        // boolean isBST;
        public int maxBSTSubtreeSize;
        int max;
        int min;
        TreeNode maxBSTSubtreeHead;

        Info(int maxBSTSubtreeSize, TreeNode maxBSTSubtreeHeadlSize, int max, int min) {
            this.maxBSTSubtreeSize = maxBSTSubtreeSize;
            this.maxBSTSubtreeHead = maxBSTSubtreeHeadlSize;
            this.min = min;
            this.max = max;

        }
    }

    static TreeNode maxSubBSTHead1(TreeNode head) {
        if (null == head) {
            return null;
        }
        return process(head).maxBSTSubtreeHead;
    }

    static Info process(TreeNode node) {
        if (node == null) {
            return null;
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);


        int maxBSTSubtreeSize = 0;
        TreeNode maxBSTSubtreeHead = null;
        int max = node.val;
        int min = node.val;


        if (null != leftInfo) {

            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            maxBSTSubtreeHead = leftInfo.maxBSTSubtreeHead;
            maxBSTSubtreeSize = leftInfo.maxBSTSubtreeSize;

        }
        if (null != rightInfo) {

            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            if (rightInfo.maxBSTSubtreeSize > maxBSTSubtreeSize) {
                maxBSTSubtreeHead = rightInfo.maxBSTSubtreeHead;
                maxBSTSubtreeSize = rightInfo.maxBSTSubtreeSize;
            }

        }


        if ((leftInfo == null || (leftInfo.maxBSTSubtreeHead == node.left && leftInfo.max < node.val))
                && (rightInfo == null || (rightInfo.maxBSTSubtreeHead == node.right && rightInfo.min > node.val))) {
            maxBSTSubtreeHead = node;
            maxBSTSubtreeSize = (leftInfo == null ? 0 : leftInfo.maxBSTSubtreeSize)
                    + (rightInfo == null ? 0 : rightInfo.maxBSTSubtreeSize) + 1;
        }

        return new Info(maxBSTSubtreeSize, maxBSTSubtreeHead, max, min);

    }

    // for test
    public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static TreeNode generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        TreeNode head = new TreeNode((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static int getBSTSize(TreeNode head) {
        if (head == null) {
            return 0;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).val <= arr.get(i - 1).val) {
                return 0;
            }
        }
        return arr.size();
    }

    public static void in(TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

    public static TreeNode maxSubBSTHead2(TreeNode head) {
        if (head == null) {
            return null;
        }
        if (getBSTSize(head) != 0) {
            return head;
        }
        TreeNode leftAns = maxSubBSTHead1(head.left);
        TreeNode rightAns = maxSubBSTHead1(head.right);
        return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
    }

    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = generateRandomBST(maxLevel, maxValue);
            if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

}
